class Solution {
    vector<vector<string>> ret;
    vector<string> success;

    bool isPalindrome(string s)
    {
        int left = 0, rigth = s.size() - 1;
        while (left <= rigth)
        {
            if (s[left] != s[rigth])
                return false;
            left++;
            rigth--;
        }
        return true;
    }

    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(success);
            return;
        }

        for (int i = pos; i < s.size(); i++)
        {
            
            string tmp = s.substr(pos, i - pos + 1);
            printf("i = %d, pos = %d, tmp: ", i, pos);
            cout << tmp << endl;
            if (isPalindrome(tmp))
            {
                success.push_back(tmp);
                dfs(s, i + 1);
                success.pop_back();
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0);

        return ret;
    }
};